Secret calculation is a technique in which data processing is performed while concealing data by secret sharing. The secret sharing is a technique in which data is converted into a plurality of distributed values so that original data can be restored by using a certain number or more number of pieces of distributed values, while original data cannot be restored by using distributed values of which the number of pieces is smaller than the certain number. The secret sharing can be categorized into several kinds. Examples of the secret sharing include (k,n)-secret sharing, permutation data secret sharing, and the like.
The (k,n)-secret sharing is secret sharing in which a plain text which is inputted is divided into n pieces of shares so as to be distributed to n pieces of parties P=(p0, . . . , pn−1) in advance. The plain text can be restored when arbitrary k pieces of shares are provided. Any information on the plain text cannot be obtained from shares of which the number is smaller than k. Specific examples of types of the (k,n)-secret sharing include Shamir secret sharing, reproduction secret sharing, and the like.
The permutation data secret sharing is secret sharing performed while concealing permutation data. The permutation data is data representing the rearrangement way in rearrangement of data columns. When m pieces of data columns are rearranged, permutation data π having the volume m is data representing a bijective map π:Nm→Nm. Here, Nm represents a collection of non-negative integers which are smaller than an arbitrary integer m. For example, data of which elements in vectors x→∈(Nm)m are different from each other can be assumed as random permutation data having the volume m.
More specifically, a vector x→=(3,0,2,1) can be assumed as random permutation data having the volume 4. For example, it is assumed to rearrange the data column y→=(1,5,7,10) by the vector x→. 1 which is the 0th element of the data column y→ is moved to the third position represented by the 0th element of the vector x→. 5 which is the first element of the data column y→ is moved to the 0th position represented by the first element of the vector x→. In a similar manner, 7 is moved to the second position and 10 is moved to the first position. As a result, the post-permutation data column z→=(5,10,7,1) is obtained.
In the permutation data secret sharing, permutation data is concealed by the following procedure. It is assumed that there are N pieces of k party groups of columns P=ρ0, . . . , ρN−1. For example, when k=2, each k party group ρi is a set (p0,p1) of the party p0 and the party p1, a set (p0,p2) of the party p0 and the party p2, or the like. It is assumed that all parties in each k party group ρi mutually share the permutation data πρi and the permutation data πρi is not informed to a complement ρ−i. Further, a corresponding plain text is assumed to be π0(π1( . . . (πN−1(I)) . . . )). Here, I represents permutation in which output is performed in the same arrangement as that of input, that is, identical permutation. In this case, if the k party groups of columns P=ρ0, . . . , ρN−1 is set so that “(condition 1) any complement ρ−i satisfies ρρ−i with respect to an arbitrary k−1 party group ρ”, any permutation data πρi is unknown in any coupling of the k−1 party.
For example, when the number n of parties satisfies n≥2k−1, the above-mentioned condition 1 is satisfied if the column P of the k party groups is set as a collection including all the k party groups. Further, when the number n of parties satisfies n>2k−1, the above-mentioned condition 1 is sometimes satisfied even if not all the k party groups are included. For example, when k=2 and n=4, the condition 1 is satisfied though {(p0,p1),(p2,p3)} does not include all the k party groups.
Secret sorting is processing for rearranging values in accordance with a certain rule based on a key order relation while concealing keys and values which are subjected to secret sharing. As a related art for performing the secret sorting, a technique described in Non-patent Literature 1 is disclosed.
In the secret sorting described in Non-patent Literature 1, a secret sharing value [v→] of the value column v→ and secret sharing values [k→L−1], . . . , [k→0] of the key column k→ are inputted and a secret sharing value [σv→] of the value column σv→ which is subjected to alignment is outputted. Here, σ is a permutation function representing sorting. (1) The permutation function σ0 is first set as identical mapping on Zm. Here, Zm is a collection of integers which are equal to or larger than 0 and smaller than m. (2) The random ID column [h→]:=[I] is set. Here, I represents identical permutation. (3) Processing from (4) to (14) described below is executed with respect to i=0, . . . , L−1. (4) The permutation data <π0>, <π1>, and <π2> are generated. (5) [σi−1k→i] is stably sorted by 1 bit so as to generate the order table [s→]. (6) Secret random permutation of ([σih→],[s→]) is performed with the permutation data <π0> so as to generate ([π0σih→],[π0s→]). (7) If i=L, the process goes to (15) described below. (8) Secret random permutation of ([h→],[k→i+1]) is performed with the permutation data <π1> so as to generate ([π1h→],[π1k→i+1]). (9) [π1h→] and [π0σih→] are restored. (10) [π0σik→i+1]:=π0σih→(π1h→)−1[π1k→i+1] is calculated. (11) Secret random permutation of ([π0σih→],[π0s→],[π0σik→i+1]) is performed with the permutation data <π2> so as to generate ([π20σih→],[π20s→],[π20σik→i+1]). Here, π20=π2π0 holds. (12) [π20s→] is restored. (13) ([s→−1σih→],[s→−1σik→i+1]):=(π20s→)−1([π20σi→],[π20σik→i+1]) is calculated. (14) Permutation function σi+1:=s→−1σi is set. (15) [π0s→] and [s→−1σih→] are restored. (16) Permutation function σL:=s→−1σL−1 is set. (17) The permutation data <π3> is generated. (18) Permutation of [h→] and [v→] is performed with the permutation data <π3> so as to generate ([π3h→],[π3v→]). (19) [π3h→] and [σLh→] are restored so as to output [σv→]:=σLh→(π3h→)−1[π3v→]. Here, permutation function σ=σL.